/*
 * @lc app=leetcode.cn id=91 lang=cpp
 *
 * [91] 解码方法
 */

// @lc code=start
class Solution
{
public:
  int numDecodings(string s)
  {
    // 不能被解码
    if (s[0] == '0')
      return 0;
    int n = s.size();
    vector<int> dp(n + 1);
    // 第一个非0的数字总有一种解码方法
    dp[0] = dp[1] = 1;
    for (int i = 2; i <= n; ++i) {
      int cur = s[i - 1] - '0', pre = s[i - 2] - '0';
      if (cur == 0) {
        if (pre == 0 || pre > 2) return 0; // 连续的0或两数大于26无法解码
        dp[i] = dp[i - 2];
      }
      else {
        dp[i] = dp[i - 1]; // 单独解码
        int com_num = pre * 10 + cur;
        // 组合解码
        if (com_num != cur && com_num <= 26)
          dp[i] += dp[i - 2];
      }
    }
    return dp[n];
  }
};
// @lc code=end
